package bfs;

import java.util.LinkedList;
import java.util.Queue;

public class ZeroOneMatrix542 {
    static int[][] vectors = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    public static int[][] updateMatrix(int[][] matrix) {
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j< matrix[0].length; j++){
                if(matrix[i][j] != 0){
                    bfs(matrix, i ,j);
                }
            }
        }
        return matrix;
    }

    public static void bfs(int[][] matrix, int i, int j){
        int step = 0;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        q.add(new int[]{i,j});
        visited[i][j] = true;
        while(!q.isEmpty()){
            int size = q.size();
            for(int k = 0; k < size; k++){
                int[] pt = q.poll();
                if(matrix[pt[0]][pt[1]] == 0){
                    matrix[i][j] = step;
                    return;
                }
                for(int[] v: vectors){
                    int adjI = pt[0] + v[0];
                    int adjJ = pt[1] + v[1];
                    if(adjI >= 0 && adjI < matrix.length && adjJ >= 0 && adjJ < matrix[0].length && !visited[adjI][adjJ]){
                        q.add(new int[]{adjI,adjJ});
                        visited[adjI][adjJ] = true;
                    }
                }
                step++;
            }
        }
    }

    public static void main(String[] args) {
        int[][] test = new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
        int[][] re = updateMatrix(test);
        System.out.println();
    }
}
